import java.util.*;

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        RandomListNode head = pHead;
        RandomListNode slow = head;
        RandomListNode fast = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while(fast.next != slow) {
            fast = fast.next;
        }
        fast.next = null;
        //新链表的头结点
        RandomListNode dum = new RandomListNode(0);
        RandomListNode cur = dum;
        fast = head;
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        //next
        while(fast != null) {
            cur.next = new RandomListNode(fast.label);
            cur = cur.next;
            map.put(fast,cur);
            fast = fast.next;
        }
        cur.next = null;
        //ramdom
        fast = pHead;
        cur = dum.next;
        while(cur != null) {
            cur.random = map.get(fast.random);
            cur = cur.next;
            fast = fast.next;
        }
        return dum.next;


    }
}
